#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include "utils.h"
using namespace std;

class Solution {
public:
    void postorderTraversal(TreeNode *root, vector<int> &v) {
        if (root == NULL) return ;
        postorderTraversal(root->left, v);
        postorderTraversal(root->right, v);
        v.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> v;
        postorderTraversal(root, v);
        return v;
    }

    void inorderTraversal(TreeNode *root, vector<int> &v) {
        if (root == NULL) return ;
        inorderTraversal(root->left, v);
        v.push_back(root->val);
        inorderTraversal(root->right, v);
    }

    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> v;
        inorderTraversal(root, v);
        return v;
    }

    void preorderTraversal(TreeNode *root, vector<int> &v) {
        if (root == NULL) return ;
        v.push_back(root->val);
        preorderTraversal(root->left, v);
        preorderTraversal(root->right, v);
    }

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> v;
        preorderTraversal(root, v);
        return v;
    }

    vector<int> preorderTraversal_iterator(TreeNode *root) {
        stack<TreeNode *> st;
        vector<int> v;
        TreeNode *p;
        if (root !=NULL) st.push(root);

        while(!st.empty()) {
            p = st.top();
            v.push_back(p->val);
            st.pop();
            if (p->right != NULL) st.push(p->right);
            if (p->left != NULL) st.push(p->left);
        }

        return v;
    }

    vector<int> inorderTraversal_iterator(TreeNode *root) {
        vector<int> v;
        stack<TreeNode *> st;

        while(root != NULL || !st.empty()) {
            if (root != NULL) {
                st.push(root);
                root = root->left;
            } else {
                root = st.top();
                v.push_back(root->val);
                st.pop();

                root = root->right;
            }
        }
        return v;
    }

    vector<int> postorderTraversal_iterator(TreeNode *root) {
        stack<TreeNode *> st;
        TreeNode *last = NULL, *p = NULL;
        vector<int> v;
        if(root == NULL) return v;
        st.push(root);

        while(!st.empty()) {
            p = st.top();
            if (p->right == NULL && (p->left == NULL || last == p->left) || p->right != NULL && last == p->right) {
                v.push_back(p->val);
                last = p;
                st.pop();
            } else if(p->left == NULL || last == p->left) {
                st.push(p->right);
            } else {
                st.push(p->left);
            }
        }
        return v;
    }

    vector<int> morrisInorderTraversal(TreeNode *root) {
        TreeNode *p = NULL;
        vector<int> v;
        while(root != NULL) {
            if (root->left == NULL) {
                v.push_back(root->val);
                root = root->right;
            } else {
                p = root->left;
                while(p->right!=NULL && p->right!=root) p = p->right;

                if(p->right == NULL) {
                    p->right = root;
                    root = root->left;
                } else {
                    p->right = NULL;
                    v.push_back(root->val);
                    root = root->right;
                }
            }
        }
        return v;
    }
    vector<int> morrisPreorderTraversal(TreeNode *root) {
        TreeNode *p = NULL;
        vector<int> v;
        while(root != NULL) {
            p = root->left;
            if (p!=NULL) {
                while(p->right!=NULL && p->right!=root) p = p->right;
                if (p->right == NULL) {
                    v.push_back(root->val);
                    p->right = root;
                    root = root->left;
                } else {
                    p->right = NULL;
                    root = root->right;
                }
            } else {
                v.push_back(root->val);
                root = root->right;
            }
        }
        return v;
    }

    vector<int> morrisPostorderTraversal(TreeNode *root) {
    }
};

int main(int argc, char *argv[])
{
    //int a[] = {3, 9, 20, -1, -1, 15, 7};
    int a[] = {5, 3, 7, 2, 4, 6, 8, 1};
    vector<int> v(a, a+sizeof(a)/sizeof(int));
    TreeNode *root = build_binary_tree(v);

    cout << "level order:" << endl;
    print_vector(levelOrder(root));

    Solution ss;
    cout << "post order:" << endl;
    print_vector(ss.postorderTraversal(root));
    print_vector(ss.postorderTraversal_iterator(root));

    cout << "in order:" << endl;
    print_vector(ss.inorderTraversal(root));
    print_vector(ss.inorderTraversal_iterator(root));
    print_vector(ss.morrisInorderTraversal(root));

    cout << "pre order:" << endl;
    print_vector(ss.preorderTraversal(root));
    print_vector(ss.preorderTraversal_iterator(root));

    return 0;
}
